//#define  _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//#include <vector>
//using namespace std;
//vector<bool> vis;
//vector<vector<pair<int, int>>> nums;
//int N, K;
////int memo[100000][100000] = {0};
//vector<vector<int>> memo;
//int dfs(int i, int j)
//{
//	if (i == j)
//		return 0;
//	int ret = INT_MAX >> 1;
//	auto v = nums[i];
//	for (auto e : v)
//	{
//		
//		int next = e.first;
//		int val = e.second;
//		if (!vis[next])
//		{
//			vis[next] = true;
//			ret = min(dfs(next, j) + val, ret);
//			vis[next] = false;
//		}
//	}
//	return ret;
//}
//
//int main()
//{
//	cin >> N >> K;
//	vector<vector<int>> arr(N, vector<int>(3));
//	memo.resize(N + 1, vector<int>(N + 1));
//	nums.resize(N + 1);
//	for (int i = 1; i < N; i++)
//	{
//		for (int j = 0; j < 3; j++)
//		{
//			cin >> arr[i][j];
//		}
//		int a = arr[i][0], b = arr[i][1], c = arr[i][2];
//		nums[a].push_back({ b, c });
//		nums[b].push_back({ a, c });
//	}
//	vis.resize(N + 1);
//
//	vector<int> path(K + 1);
//	for (int i = 1; i <= K; i++)
//		cin >> path[i];
//
//	for (int i = 1; i <= K; i++)
//	{
//		int sum = 0;
//		for (int j = 1; j < K; j++)
//		{
//			if (i == j || i == K && j + 1 == K)
//				continue;
//			else if (i == j + 1 && j + 2 <= K)
//				sum += dfs(path[j], path[j + 2]), j++;
//			else
//				sum += dfs(path[j], path[j + 1]);
//		}
//		cout << sum << " ";
//	}
//}